#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e5+10;
int n,cnt,root,a[MAXN],f[MAXN],len,ans[MAXN];
struct point
{
	int pri,lc,rc,siz;
}p[MAXN];
void push_up(int o)
{
	p[o].siz=p[p[o].lc].siz+p[p[o].rc].siz+1;
	return;
}
void lturn(int &o)
{
	int t=p[o].rc;
	p[o].rc=p[t].lc;
	p[t].lc=o;
	p[t].siz=p[o].siz;
	push_up(o);
	o=t;
	return;
}
void rturn(int &o)
{
	int t=p[o].lc;
	p[o].lc=p[t].rc;
	p[t].rc=o;
	p[t].siz=p[o].siz;
	push_up(o);
	o=t;
	return;
}
void insert(int &o,int rank)
{
	if(!o)
	{
		p[o=++cnt]=(point){rand(),0,0,1};
		return;
	}
	++p[o].siz;
	if(rank<=p[p[o].lc].siz)
	{
		insert(p[o].lc,rank);
		if(p[p[o].lc].pri>p[o].pri)rturn(o);
	}
	else
	{
		insert(p[o].rc,rank-p[p[o].lc].siz-1);
		if(p[p[o].rc].pri>p[o].pri)lturn(o);
	}
	return;
}
void dfs(int o)
{
	if(!o)return;
	dfs(p[o].lc);
	a[++cnt]=o;
	dfs(p[o].rc);
	return;
}
void LIS()
{
	for(int i=1;i<=n;++i)
	{
		int l=1,r=len;
		if(a[i]>f[len])
		{
			f[++len]=a[i];
			ans[a[i]]=len;
			continue;
		}
		while(l<r)
		{
			int mid=(l+r)>>1;
			if(a[i]>f[mid])l=mid+1;
			else r=mid;
		}
		f[l]=a[i];
		ans[a[i]]=l;
	}
	return;
}
int main()
{
	scanf("%d",&n);
    srand(n);
	for(int i=1;i<=n;++i)
	{
		int x;
		scanf("%d",&x);
		insert(root,x);
	}
	cnt=0;
	dfs(root);
	LIS();
	for(int i=1;i<=n;++i)
	{
		ans[i]=max(ans[i-1],ans[i]);
		printf("%d\n",ans[i]);
	}
	return 0;
}
